Matrix Structure

Matrix inversion

• Suppose \(\mathbf{X}\) is an \(n \times n\) matrix

• Find the matrix \(\mathbf{X}^{-1}\) such that

  \[ \mathbf{X}^{-1} \mathbf{X} = \mathbf{X} \mathbf{X}^{-1} = \mathbf{I} \]

• Why?
  • Solve systems of equations
  • Perform linear regression
  • Provide intuition about colinearity, fixed effects, and other relevant design matricies for social scientists

Calculating matrix inversions

\[ \begin{aligned} x_{1} + x_{2} + x_{3} &= 0 \\ 0x_{1} + 5x_{2} + 0x_{3} & = 5 \\ 0 x_{1} + 0 x_{2} + 3 x_{3} & = 6 \\ \end{aligned} \]

• \(\mathbf{A} = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 5 & 0 \\ 0 & 0 & 3 \end{pmatrix}\)
• \(\mathbf{x} = (x_{1} , x_{2}, x_{3} )\)

• \(\mathbf{b} = (0, 5, 6)\)

• System of equations

  \[ \begin{eqnarray} \mathbf{A}\mathbf{x} &=& \mathbf{b} \end{eqnarray} \]

  • \(\mathbf{A}^{-1}\) exists if and only if \(\mathbf{A}\mathbf{x} = \mathbf{b}\) has only one solution

Definition

• Suppose \(\mathbf{X}\) is an \(n \times n\) matrix

• We will call \(\mathbf{X}^{-1}\) the inverse of \(\mathbf{X}\) if

  \[ \mathbf{X}^{-1} \mathbf{X} = \mathbf{X} \mathbf{X}^{-1} = \mathbf{I} \]

• If \(\mathbf{X}^{-1}\) exists then \(\mathbf{X}\) is invertible

• If \(\mathbf{X}^{-1}\) does not exist, then we will say \(\mathbf{X}\) is singular

Does the inverse exist?

• \(\mathbf{A}\)

  ##      [,1] [,2] [,3]
  ## [1,]    1    1    1
  ## [2,]    0    5    0
  ## [3,]    0    0    3

• \(\mathbf{A}^{-1}\)

  ##      [,1] [,2]   [,3]
  ## [1,]    1 -0.2 -0.333
  ## [2,]    0  0.2  0.000
  ## [3,]    0  0.0  0.333

When do inverses exist

• Linear independence

1. Consider \(\mathbf{v}_{1} = (1, 0, 0)\), \(\mathbf{v}_{2} = (0,1,0)\), \(\mathbf{v}_{3} = (0,0,1)\)

2. Consider \(\mathbf{v}_{1} = (1, 0, 0)\), \(\mathbf{v}_{2} = (0,1,0)\), \(\mathbf{v}_{3} = (0,0,1)\), \(\mathbf{v}_{4} = (1, 2, 3)\)

   • \(\mathbf{v}_{4} = \mathbf{v}_{1} + 2 \mathbf{v}_{2} + 3\mathbf{v}_{3}\)

Application to regression analysis

• For each \(i\) (individual) we observe covariates \(x_{i1}, x_{i2}, \ldots, x_{ik}\) and independent variable \(Y_{i}\)

  \[ \begin{eqnarray} Y_{1} & = & \beta_{0} + \beta_{1} x_{11} + \beta_{2} x_{12} + \ldots + \beta_{k} x_{1k} \\ Y_{2} & = & \beta_{0} + \beta_{1} x_{21} + \beta_{2} x_{22} + \ldots + \beta_{k} x_{2k} \\ \vdots & \vdots & \vdots \\ Y_{i} & = & \beta_{0} + \beta_{1} x_{i1} + \beta_{2} x_{i2} + \ldots + \beta_{k} x_{ik} \\ \vdots & \vdots & \vdots \\ Y_{n} & = & \beta_{0} + \beta_{1} x_{n1} + \beta_{2} x_{n2} + \ldots + \beta_{k} x_{nk} \end{eqnarray} \]

Application to regression analysis

• \(\mathbf{x}_{i} = (1, x_{i1}, x_{i2}, \ldots, x_{ik})\)
• \(\mathbf{X} = \begin{pmatrix} \mathbf{x}_{1}\\\mathbf{x}_{2}\\ \vdots \\ \mathbf{x}_{n} \end{pmatrix}\)
• \(\boldsymbol{\beta} = (\beta_{0}, \beta_{1}, \ldots, \beta_{k} )\)
• \(\mathbf{Y} = (Y_{1}, Y_{2}, \ldots, Y_{n})\)

Application to regression analysis

\[ \begin{eqnarray} \mathbf{Y} & = & \mathbf{X}\mathbf{\beta} \\ \mathbf{X}^{'} \mathbf{Y} & = & \mathbf{X}^{'} \mathbf{X} \mathbf{\beta} \\ (\mathbf{X}^{'}\mathbf{X})^{-1} \mathbf{X}^{'} \mathbf{Y} & = & (\mathbf{X}^{'}\mathbf{X})^{-1}\mathbf{X}^{'} \mathbf{X} \mathbf{\beta} \\ (\mathbf{X}^{'}\mathbf{X})^{-1} \mathbf{X}^{'} \mathbf{Y} & = &\mathbf{\beta} \end{eqnarray} \]

• Depends on \((\mathbf{X}^{'}\mathbf{X})^{-1}\) being invertible

Tax benefits of charitable contributions

• Company earns before-tax profits of $100,000
• 10% contribution of after-tax profits to charity
• State tax is 5% of profits (after charitable deduction)
• Federal tax is 40% of profits (after charitable and state tax deduction)
• How much does the company pay in state taxes, federal taxes, and Red Cross donation?

Tax benefits of charitable contributions

\[ \begin{eqnarray} C & + & 0.1S & + & 0.1F & = & 10{,}000 \\ 0.05C & + & S & && = & 5{,}000 \\ 0.4C & + & 0.4S & + & F & = & 40{,}000 \end{eqnarray} \]

Solve via matrix inversion

• \(\mathbf{A}\)

  ##      [,1] [,2] [,3]
  ## [1,] 1.00  0.1  0.1
  ## [2,] 0.05  1.0  0.0
  ## [3,] 0.40  0.4  1.0

• \(\mathbf{b}\)

  ## [1] 10000  5000 40000

• \(\mathbf{A}^{-1} \mathbf{b}\)

  ## [1]  5956  4702 35737

Matrix decomposition

• Matrix decomposition

• LU decomposition

  \[\mathbf{A} = \mathbf{L}\mathbf{U}\]

  • \(\mathbf{L}\) is a lower triangular matrix
  • \(\mathbf{U}\) is an upper triangular matrix
  • Only works for square matricies

• Other methods of decomposition

Dimension reduction

• Decreasing the number of dimensions in your dataset
• Visualize a lot of variables
• Implement supervised learning more efficiently
• Identify a smaller number of representative variables/vectors/columns that collectively explain most of the variability in the original dataset

DW-NOMINATE

• Studying legislative voting
• Roll-call votes
• Multidimensional scaling techniques
• DW-NOMINATE dimensions
  • Ideology (liberal-conservative)
  • Issue of the day

Singular value decomposition

• SVD
• Works with any rectangular matrix (not just square matricies)

Singular value decomposition

• Suppose \(\mathbf{M}\) is an \(m \times n\) matrix. There exists a factorization of the form

  \[\mathbf{M} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^{*}\]

  • \(\mathbf{U}\) is an \(m \times n\) matrix
  • \(\boldsymbol{\Sigma}\) is an \(n \times n\) diagonal matrix
  • \(\mathbf{V}^{*}\) is the transpose of an \(n \times n\) matrix

Image compression

Lion as matrix

##       [,1]  [,2]  [,3]  [,4]  [,5]
## [1,] 0.361 0.369 0.381 0.393 0.403
## [2,] 0.365 0.373 0.385 0.397 0.407
## [3,] 0.369 0.377 0.389 0.399 0.411
## [4,] 0.377 0.385 0.395 0.407 0.420
## [5,] 0.388 0.391 0.403 0.416 0.424

SVD of lion

• \(\mathbf{U}\)

  ##         [,1]    [,2]     [,3]     [,4]     [,5]
  ## [1,] -0.0398 -0.0291 -0.02032 0.019709 -0.01329
  ## [2,] -0.0405 -0.0150 -0.00198 0.000273 -0.00208
  ## [3,] -0.0396 -0.0186 -0.01972 0.020905  0.01126
  ## [4,] -0.0390 -0.0264 -0.02890 0.039385  0.01012
  ## [5,] -0.0398 -0.0300 -0.03199 0.037500  0.00553

• \(\boldsymbol{\Sigma}\)

  ##      [,1] [,2] [,3] [,4] [,5]
  ## [1,]  193  0.0  0.0    0  0.0
  ## [2,]    0 29.2  0.0    0  0.0
  ## [3,]    0  0.0 16.2    0  0.0
  ## [4,]    0  0.0  0.0   15  0.0
  ## [5,]    0  0.0  0.0    0 12.2

• \(\mathbf{V}^{*}\)

  ##         [,1]    [,2]   [,3]   [,4]    [,5]
  ## [1,] -0.0556 0.00838 0.0211 0.0377 -0.0119
  ## [2,] -0.0558 0.00848 0.0179 0.0391 -0.0131
  ## [3,] -0.0560 0.00874 0.0138 0.0405 -0.0146
  ## [4,] -0.0561 0.00888 0.0114 0.0405 -0.0159
  ## [5,] -0.0561 0.00874 0.0102 0.0394 -0.0159

Recovering the data

\[\mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^{*}\]

##       [,1]  [,2]  [,3]  [,4]  [,5]
## [1,] 0.361 0.369 0.381 0.393 0.403
## [2,] 0.365 0.373 0.385 0.397 0.407
## [3,] 0.369 0.377 0.389 0.399 0.411
## [4,] 0.377 0.385 0.395 0.407 0.420
## [5,] 0.388 0.391 0.403 0.416 0.424

Reducing the data

• Diagonal elements of \(\boldsymbol{\Sigma}\)

  ##   [1] 193.4417  29.1733  16.1600  14.9806  12.1708  11.3756  10.5788
  ##   [8]   8.9693   8.3404   7.6359   7.4752   6.8798   6.1244   5.9575
  ##  [15]   5.5327   5.3978   5.1953   4.8511   4.6521   4.6020   4.2501
  ##  [22]   4.1820   4.0820   4.0382   3.8938   3.8375   3.7173   3.5563
  ##  [29]   3.5273   3.4986   3.4396   3.4027   3.3417   3.2681   3.2025
  ##  [36]   3.1409   3.0671   3.0221   3.0124   2.9543   2.8912   2.8365
  ##  [43]   2.8076   2.7306   2.6768   2.6547   2.6008   2.5562   2.5353
  ##  [50]   2.5186   2.4892   2.4669   2.3997   2.3361   2.3274   2.2823
  ##  [57]   2.2424   2.2378   2.1923   2.1692   2.1122   2.0840   2.0704
  ##  [64]   2.0510   2.0241   2.0196   1.9849   1.9568   1.9305   1.9237
  ##  [71]   1.9052   1.8737   1.8433   1.8222   1.8107   1.7891   1.7699
  ##  [78]   1.7554   1.7195   1.7039   1.6870   1.6695   1.6453   1.6310
  ##  [85]   1.6101   1.5815   1.5727   1.5373   1.5198   1.5105   1.4861
  ##  [92]   1.4748   1.4609   1.4378   1.4321   1.4016   1.4001   1.3788
  ##  [99]   1.3624   1.3386   1.3301   1.3169   1.3057   1.2704   1.2593
  ## [106]   1.2419   1.2376   1.2065   1.1922   1.1825   1.1741   1.1584
  ## [113]   1.1405   1.1314   1.1157   1.1003   1.0921   1.0705   1.0602
  ## [120]   1.0480   1.0406   1.0314   1.0191   0.9983   0.9939   0.9919
  ## [127]   0.9634   0.9500   0.9434   0.9337   0.9213   0.9153   0.9044
  ## [134]   0.8910   0.8777   0.8528   0.8458   0.8419   0.8246   0.8196
  ## [141]   0.8005   0.7967   0.7924   0.7866   0.7734   0.7591   0.7564
  ## [148]   0.7469   0.7365   0.7283   0.7198   0.7159   0.7118   0.7009
  ## [155]   0.6926   0.6874   0.6817   0.6634   0.6552   0.6517   0.6493
  ## [162]   0.6352   0.6184   0.6127   0.6073   0.6039   0.6014   0.5949
  ## [169]   0.5915   0.5810   0.5767   0.5627   0.5547   0.5456   0.5381
  ## [176]   0.5351   0.5310   0.5247   0.5211   0.5139   0.5025   0.4998
  ## [183]   0.4966   0.4808   0.4763   0.4725   0.4613   0.4552   0.4529
  ## [190]   0.4471   0.4411   0.4374   0.4326   0.4309   0.4232   0.4178
  ## [197]   0.4152   0.4047   0.4005   0.3970   0.3884   0.3795   0.3790
  ## [204]   0.3770   0.3705   0.3690   0.3597   0.3535   0.3506   0.3465
  ## [211]   0.3434   0.3387   0.3341   0.3243   0.3201   0.3183   0.3099
  ## [218]   0.3073   0.3020   0.2980   0.2972   0.2953   0.2911   0.2826
  ## [225]   0.2787   0.2738   0.2705   0.2644   0.2584   0.2542   0.2533
  ## [232]   0.2472   0.2424   0.2397   0.2356   0.2320   0.2300   0.2268
  ## [239]   0.2205   0.2187   0.2160   0.2096   0.2077   0.1980   0.1961
  ## [246]   0.1930   0.1895   0.1891   0.1853   0.1814   0.1798   0.1772
  ## [253]   0.1720   0.1704   0.1681   0.1658   0.1650   0.1617   0.1539
  ## [260]   0.1523   0.1483   0.1457   0.1436   0.1424   0.1367   0.1360
  ## [267]   0.1332   0.1304   0.1276   0.1265   0.1259   0.1232   0.1201
  ## [274]   0.1158   0.1119   0.1112   0.1079   0.1069   0.1044   0.1010
  ## [281]   0.0993   0.0980   0.0934   0.0905   0.0900   0.0878   0.0868
  ## [288]   0.0847   0.0838   0.0796   0.0763   0.0744   0.0733   0.0710
  ## [295]   0.0682   0.0674   0.0671   0.0637   0.0612   0.0595   0.0570
  ## [302]   0.0556   0.0537   0.0501   0.0485   0.0446   0.0435   0.0426
  ## [309]   0.0401   0.0361   0.0354   0.0336   0.0311   0.0295   0.0286
  ## [316]   0.0257   0.0248   0.0238   0.0235   0.0233   0.0224   0.0221
  ## [323]   0.0218   0.0208   0.0203   0.0200   0.0195   0.0191   0.0184
  ## [330]   0.0181   0.0175   0.0174   0.0170   0.0162   0.0157   0.0155
  ## [337]   0.0152

Reducing the data

Principal components analysis

• Find a low-dimensional representation of the data that contains as much as possible of the variation
• Dimensions are linear combinations of the variables

Calculating the PCA

1. Rescale each column to be mean 0 and standard deviation 1
2. Compute the covariance matrix \(\mathbf{S}\). Here \(\mathbf{X}\) is a data matrix: \[\mathbf{S} = \dfrac{1}{N} \mathbf{X}' \mathbf{X}\]
3. Compute the \(K\) largest eigenvectors of \(\mathbf{S}\)
   • Eigenvector - principal directions
   • Values of observations along eigenvector - principal components
   • Eigenvalue - amount of variance along the eigenvector

• Not an efficient approach
• Let’s use SVD!

Calculating the PCA

\[\mathbf{M} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^{*}\]

• \(\mathbf{V}^{*}\) = principal directions (eigenvector)
• Columns of \(\mathbf{U} \boldsymbol{\Sigma}\) = principal components (values along eigenvector)
• Values of the diagonal elements of \(\boldsymbol{\Sigma}\) \(\approx\) eigenvalues

USArrests

##            Murder Assault UrbanPop Rape
## Alabama      13.2     236       58 21.2
## Alaska       10.0     263       48 44.5
## Arizona       8.1     294       80 31.0
## Arkansas      8.8     190       50 19.5
## California    9.0     276       91 40.6
## Colorado      7.9     204       78 38.7

Biplot of USArrests